package leetcode;

import java.util.Stack;

public class Pattern132 {

	public static void main(String[] args) {
		Pattern132 object = new Pattern132();
		int[] nums = {-10, -10, -10, -9, -10, -9, -10, -9, -10, -9, -9, -10, -9, -9};
		System.out.println(object.find132pattern(nums));
	}

	
	//空间超了
	public boolean find132pattern(int[] nums) {
        if(nums == null || nums.length <= 0){
            return false;
        }
        //recore max value in thr range of i - j
        int[][] max = new int[nums.length][nums.length];
        for(int i = 0; i < nums.length - 1; i++){
        	max[i][i] = Integer.MIN_VALUE;
            for(int k = i + 1; k < nums.length; k++){
                max[i][k] = Math.max(max[i][k - 1], nums[k]);
            }
        }
        for(int i = 0; i < nums.length - 2; i++){
            for(int k = nums.length - 1; k > i + 1; k--){
                if(nums[k] <= nums[i]){
                    continue;
                }else{
                    if(max[i][k] > nums[k]){
                    	System.out.println("i :" + i + " k :" + k + " " + max[i][k]);
                        return true;
                    }
                }
            }
        }
        return false;
    }
	
	//https://discuss.leetcode.com/topic/67881/single-pass-c-o-n-space-and-time-
	//solution-8-lines-with-detailed-explanation
	
	public boolean find132pattern_2(int[] nums) {
	    Stack<Integer> stack = new Stack<>();
	    
	    //首先将k入栈
	    //two表示的是nums[k]
	    for (int i = nums.length - 1, two = Integer.MIN_VALUE; i >= 0; i--){
	        if (nums[i] < two){
	        	return true;
	        }else {
	        	//如果nums[i] 大于栈中的第一个元素
	        	//那么栈中的第一个数就要变为第二个数
	        	//比如初始有2， 遇到3，那么就将2出栈，并将two赋值给two
	        	//之后我们把3入栈了，所以栈只有1个元素
	        	//就以1332为例，进栈2，进栈3,然后two = 2，遇到3的时候不做操作，遇到1，小于two返回
	        	//再以46345为例，栈中有5 4 3，遇到6, 3出栈 4 出栈 5 出栈. two = 5, 6进栈
	        	//接下来找是否有比5小的元素
	        	for (; !stack.empty() && nums[i] > stack.peek();){
	        		two = Math.max(two, stack.pop());
	        	}
	        }
	        stack.push(nums[i]);
	    }
	    return false;
	}
}
